{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Beauty of All Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: beautySum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有子字符串美丽值之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个字符串的 <strong>美丽值</strong> 定义为：出现频率最高字符与出现频率最低字符的出现次数之差。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，<code>\"abaacc\"</code> 的美丽值为 <code>3 - 1 = 2</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个字符串 <code>s</code> ，请你返回它所有子字符串的 <strong>美丽值</strong> 之和。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aabcb\"\n",
    "<b>输出：</b>5\n",
    "<strong>解释：</strong>美丽值不为零的字符串包括 [\"aab\",\"aabc\",\"aabcb\",\"abcb\",\"bcb\"] ，每一个字符串的美丽值都为 1 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"aabcbaa\"\n",
    "<b>输出：</b>17\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= s.length <=<sup> </sup>500</code></li>\n",
    "\t<li><code>s</code> 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-beauty-of-all-substrings](https://leetcode.cn/problems/sum-of-beauty-of-all-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-beauty-of-all-substrings](https://leetcode.cn/problems/sum-of-beauty-of-all-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aabcb\"', '\"aabcbaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            Dict = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i,n):\n",
    "                Dict[s[j]]+= 1\n",
    "                mx = max(mx,Dict[s[j]])\n",
    "                ans += mx - min(Dict.values())\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        result = 0\n",
    "        char_dict = defaultdict(int)\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length + 1):\n",
    "                char_dict[s[j - 1]] += 1\n",
    "                value_list = list(char_dict.values())\n",
    "                if len(char_dict) >= 2:\n",
    "                    result += max(value_list) - min(value_list)\n",
    "            char_dict.clear()\n",
    "\n",
    "\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            cnt = [0] * 26\n",
    "            cnt[ord(s[i]) - ord('a')] = 1\n",
    "            for j in range(i + 1, n):\n",
    "                cnt[ord(s[j]) - ord('a')] += 1\n",
    "                mi, ma = 1000, 0\n",
    "                for k in range(26):\n",
    "                    if cnt[k]:\n",
    "                        mi = min(mi, cnt[k])\n",
    "                        ma = max(ma, cnt[k])\n",
    "                ret += ma - mi\n",
    "        return ret\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        result = 0\n",
    "        char_dict = defaultdict(int)\n",
    "        for i in range(length):\n",
    "            max_ = 0\n",
    "            for j in range(i + 1, length + 1):\n",
    "                char_dict[s[j - 1]] += 1\n",
    "                max_ = max(max_, char_dict[s[j - 1]])\n",
    "                result += max_ - min(char_dict.values())\n",
    "            char_dict.clear()\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            C = Counter()\n",
    "            for j in range(i, n):\n",
    "                C[s[j]] += 1\n",
    "                ans += max(C.values()) - min(C.values())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        result = 0\n",
    "        char_dict = defaultdict(int)\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length + 1):\n",
    "                char_dict[s[j - 1]] += 1\n",
    "                value_list = list(char_dict.values())\n",
    "                if len(char_dict) >= 2:\n",
    "                    result += max(value_list) - min(value_list)\n",
    "            char_dict.clear()\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                res += mx - min(cnt.values())\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        result = 0\n",
    "        char_dict = defaultdict(int)\n",
    "        for i in range(length):\n",
    "            max_ = 0\n",
    "            for j in range(i + 1, length + 1):\n",
    "                char_dict[s[j - 1]] += 1\n",
    "                max_ = max(max_, char_dict[s[j - 1]])\n",
    "                result += max_ - min(char_dict.values())\n",
    "            char_dict.clear()\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0,len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i,n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values())-min(cnt.values())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                res += mx - min(cnt.values())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(s)):\n",
    "            nums = Counter()\n",
    "            for j in range(i, len(s)):\n",
    "                nums[s[j]] += 1\n",
    "                ans += max(nums.values()) - min(nums.values())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = Counter(s[i])\n",
    "            for j in range(i+1, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                res += max(cnt.values()) - min(cnt.values())\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            counter = defaultdict(int)\n",
    "            min_val, max_val = float(\"inf\"), float(\"-inf\")\n",
    "            for j in range(i, n):\n",
    "                counter[s[j]] += 1\n",
    "                min_val = min(counter.values())\n",
    "                max_val = max(counter[s[j]], max_val)\n",
    "                result += max_val - min_val\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        count = 0\n",
    "        for i in range(0, l - 2):\n",
    "            cnt = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                count += mx - min(cnt.values())\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            mp = {}\n",
    "            maxcnt = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(s[j] not in mp):\n",
    "                    mp[s[j]] = 1\n",
    "                else:\n",
    "                    mp[s[j]] += 1\n",
    "                maxcnt = max(maxcnt, mp[s[j]])\n",
    "                mincnt = min(mp.values())\n",
    "                result += maxcnt - mincnt\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            mp = defaultdict(int)\n",
    "            for j in range(i, n):\n",
    "                mp[s[j]] += 1\n",
    "                ans += max(mp.values()) - min(mp.values())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        # 超时了，看来只能O(n^2)的时间复杂度才能完成了\n",
    "        # bigferfix = [[0]*(len(s)+1) for _ in range(26)]\n",
    "        # for j in range(1,len(s)+1):\n",
    "        #     for k in range(26):\n",
    "        #         bigferfix[k][j] = bigferfix[k][j-1]\n",
    "        #     bigferfix[ord(s[j-1])-ord('a')][j] += 1\n",
    "        # # 枚举每个区间的字母的最大值、最小值\n",
    "        # res = 0\n",
    "        # for i in range(len(s)):\n",
    "        #     for j in range(i+1,len(s)):\n",
    "        #         # 枚举的是(i,j) j是从i+1开始的\n",
    "        #         min_count = inf \n",
    "        #         max_count = -inf\n",
    "        #         for k in range(26):\n",
    "        #             a = bigferfix[k][j+1] - bigferfix[k][i]\n",
    "        #             if a == 0:\n",
    "        #                 continue \n",
    "        #             min_count = min(min_count,a)\n",
    "        #             max_count = max(max_count,a)\n",
    "        #         res += max_count-min_count\n",
    "        # return res\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                res += mx - min(cnt.values())\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        \n",
    "        def cal(s):\n",
    "            counter = Counter(s)\n",
    "            min_val, max_val = float(\"inf\"), float(\"-inf\")\n",
    "            for v in counter.values():\n",
    "                if v < min_val:\n",
    "                    min_val = v\n",
    "                if v > max_val:\n",
    "                    max_val = v\n",
    "            return max_val - min_val\n",
    "\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1, n):\n",
    "                result += cal(s[i: j+1])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "\n",
    "\n",
    "                \n",
    "        su=0\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i+1,len(s)):\n",
    "                    counter=collections.Counter(s[i:j+1])\n",
    "                    v=max(counter.values())-min(counter.values())\n",
    "                    # print(counter.values())\n",
    "                    # print(v,max(counter.values()),min(counter.values()))\n",
    "                    \n",
    "                    su+=v\n",
    "        return su"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = dict()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                if s[j] not in cnt:\n",
    "                    cnt[s[j]] = 1\n",
    "                else:\n",
    "                    cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                res += mx - min(cnt.values())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        result = 0\n",
    "        char_dict = defaultdict(int)\n",
    "        for i in range(length):\n",
    "            for j in range(i + 1, length + 1):\n",
    "                char_dict[s[j - 1]] += 1\n",
    "                value_list = char_dict.values()\n",
    "                result += max(value_list) - min(value_list)\n",
    "                    \n",
    "            char_dict.clear()\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                res += mx - min(cnt.values())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)-1):\n",
    "            cnt = collections.Counter()\n",
    "            maxv = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                maxv = max(maxv, cnt[s[j]])\n",
    "                res += maxv - min(cnt.values())\n",
    "        return res\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        count = 0\n",
    "        for i in range(0, l - 2):\n",
    "            d = {}\n",
    "            for j in range(i + 3, l + 1):\n",
    "                if not d:\n",
    "                    d = dict(Counter(s[i:j]))\n",
    "                else:\n",
    "                    d[s[j - 1]] = d.get(s[j - 1], 0) + 1\n",
    "                count += max(d.values()) - min(d.values())\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            mp = {}\n",
    "            maxcnt = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(s[j] not in mp):\n",
    "                    mp[s[j]] = 1\n",
    "                else:\n",
    "                    mp[s[j]] += 1\n",
    "                maxcnt = max(maxcnt, mp[s[j]])\n",
    "                mincnt = min(mp.values())\n",
    "                result += maxcnt - mincnt\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def get_index(s):\n",
    "    return ord(s) - 97\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        _sum = 0\n",
    "    \n",
    "        l = len(s)\n",
    "        for i in range(l):\n",
    "            m = [0] * 26\n",
    "            m[get_index(s[i])] += 1\n",
    "            for j in range(i+1, l):\n",
    "                # print('开始于', i, '字母为', s[i], '结束于', j, '字母为', s[j], '字符串', s[i:j+1])\n",
    "                m[get_index(s[j])] += 1\n",
    "                # print(m)\n",
    "                n = [cnt for cnt in m if cnt > 0]\n",
    "                beauty = max(n) - min(n)\n",
    "                # print('beauty', beauty)\n",
    "                _sum += beauty\n",
    "            m[get_index(s[i])] -= 1\n",
    "            \n",
    "        return _sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            hashdict=collections.Counter()\n",
    "            for j in range(i,n):\n",
    "                hashdict[s[j]]+=1\n",
    "                ans+=max(hashdict.values())-min(hashdict.values())\n",
    "\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        ans, n = 0, len(s)\n",
    "        for i in range(n):\n",
    "            cnt = Counter()\n",
    "            for j in range(i, n):\n",
    "                cnt[s[j]] += 1\n",
    "                ans += max(cnt.values()) - min(cnt.values())\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "\n",
    "        for k in range(n):\n",
    "            dic = Counter()\n",
    "            for i in range(k,n):\n",
    "                dic[s[i]] += 1\n",
    "                freq = dic.values()\n",
    "                ans += max(freq) - min(freq)\n",
    "\n",
    "        return ans        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def beautySum(self, s: str) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            cnt = Counter()\n",
    "            mx = 0\n",
    "            for j in range(i, len(s)):\n",
    "                cnt[s[j]] += 1\n",
    "                mx = max(mx, cnt[s[j]])\n",
    "                res += mx - min(cnt.values())\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
